import java.util.*;

public class Solution {
    public static void main2(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        largestValues(root);

    }
    public static List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            while (size != 0){
                TreeNode top = queue.poll();
                max = Math.max(top.val,max);
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            }
            ret.add(max);
        }
        return ret;
    }
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k,(o1,o2)->(o1[1]-o2[1]));
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for(int key : map.keySet()){
            if(pq.size() < k) {
                pq.offer(new int[]{key,map.get(key)});
            }else{
                if(map.get(key) > pq.peek()[1]) {
                    pq.poll();
                    pq.offer(new int[]{key,map.get(key)});
                }
            }
        }
        int[] ans = new int[pq.size()];
        int index = 0;
        while (!pq.isEmpty()){
            ans[index++] = pq.poll()[0];
        }
        return ans;
    }

    public static void main0(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1,1,2};
        int[] nums2 = {1,2,3};
        System.out.println(solution.kSmallestPairs(nums1, nums2, 2));
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k,(o1,o2)->(o2[0]+o2[1]-o1[0]-o1[1]));
        for(int left : nums1) {
            for(int right : nums2) {
                pq.offer(new int[]{left,right});
            }
        }
        List<List<Integer>> list = new ArrayList<>();
        int size = pq.size();
        while (size-- != 0) {
            List<Integer> ret = new ArrayList<>();
            ret.add(pq.peek()[0]);
            ret.add(pq.peek()[1]);
            pq.poll();
            list.add(ret);
        }
            return list;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        String[] str = sentence.split(" ");
        Collections.sort(dictionary);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length; i++) {
            for(String s : dictionary){
                if(str[i].startsWith(s)){
                    str[i] = s;
                    break;
                }
            }
            sb.append(str[i]);
            if(i!=str.length-1) sb.append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        Solution solution = new Solution();
        int[] arr = solution.relativeSortArray(arr1,arr2);
        System.out.println(arr);
    }
        public int[] relativeSortArray(int[] arr1, int[] arr2) {
            int[] tmp = new int[1001];
            for (int val : arr1) {
                tmp[val]++;
            }
            int index = 0;
            int[] res = new int[arr1.length];
            for(int val : arr2) {
                while(tmp[val]-- != 0) {
                    res[index++] = val;
                }
            }
            for(int i = 0; i < 1001; i++) {
                if(tmp[i] != 0) {
                    while(tmp[i]-- != 0) {
                        res[index++] = i;
                    }
                }
            }
            return res;
        }
}